package hot100;


/*
 * Author：江松
 * Date：2023/4/19 10:13
 *
 *
 正则表达式匹配：
 动态规划
dp(i,j)为s串前i个与p串的前j个是否匹配
讨论：
si=pj||pj=.  取决于前面1个字符dp(i,j)=dp(i-1,j-1)
si!=pj pj!=* false
pj=* 可以不选择匹配,把a*看做一个整体 dp(i,j)=dp(i,j-2)
如果前面的i与j-1位置的相等，则可以匹配，且可匹配多次  dp(i,j)=dp(i-1,j)

注意初始化空串的情况
 */

public class Main10 {
    public boolean isMatch(String s, String p) {
        int slen=s.length(),plen=p.length();
        boolean dp[][]=new boolean[slen+1][plen+1];

        //初始化，空串的情况
        dp[0][0]=true;
        for(int i=2;i<=plen;++i){
            if(p.charAt(i-1)=='*')dp[0][i]=dp[0][i-2];
        }

        for(int i=1;i<=slen;++i){
            for(int j=1;j<=plen;++j){
                char sc=s.charAt(i-1);
                char pc=p.charAt(j-1);
                if(sc==pc||pc=='.')dp[i][j]=dp[i-1][j-1];
                else{
                    if(pc!='*')dp[i][j]=false;
                    else{
                        //可以选择不匹配,满足条件才匹配
                        if(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.')dp[i][j]=dp[i-1][j];
                        dp[i][j]|=dp[i][j-2];
                    }
                }
            }
        }

        return dp[slen][plen];
    }
}
